package datastructure.ch03_linked.ch04_dummyhead;

/**
 * @author guodd
 * @version 1.0
 * 设置链表的虚拟头节点
 */
public class LinkedList<E> {
    public static void main(String[] args) {
        LinkedList<Integer> links = new LinkedList<>();
        links.addFirst(1);
        links.addFirst(2);
        links.addFirst(3);
        links.addFirst(4);
        System.out.println(links);
    }

    private static class Node<E> {
        // 数据域
        E e;
        // 指针域（节点域），指向下一个节点（对象）
        public Node<E> next;

        public Node(E e, Node<E> next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    // 链表的虚拟头节点
    Node<E> dummyHead;
    // 链表中的元素个数
    private int size;

    public LinkedList() {
        dummyHead = new Node<>(null, null);
        size = 0;
    }

    // 获取链表中的元素个数
    public int getSize() {
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在链表的index(0-based)位置添加新的元素e，在链表中不是一个常用的操作，练习用
    public void add(int index, E e) {
        checkRangeAdd(index);
        Node<E> prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = new Node<>(e, prev.next);
        size++;
    }

    public void checkRangeAdd(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
    }

    // 在链表头添加新的元素e
    public void addFirst(E e) {
        add(0, e);
    }

    // 在链表末尾添加新的元素e
    public void addLast(E e) {
        add(size, e);
    }
}
